package com.foxzzz.array;

import java.util.Arrays;

/**
 * @Author wujie
 * @Class Solution338
 * @Description
 * @Date 2021/3/3 9:01
 */
public class Solution338 {
    public int[] countBits(int num) {
        /*
        0
        1 10
        11 100
        101 110 111 1000

        */
        int[] res = new int[num + 1];
        if (num >= 0) {
            res[0] = 0;
        }
        if (num >= 1) {
            res[1] = 1;
        }
        if (num >= 2) {
            int flag = 1;
            for (int i = 2; i < num + 1; i++) {
                if (i == 2 * flag) {
                    res[i] = 1;
                    flag = 2 * flag;
                } else {
                    res[i] = res[i - flag] + 1;
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        //[0,1,1,2,1,2]
        int[] ints = new Solution338().countBits(5);
        System.out.println(Arrays.toString(ints));
    }
}
